﻿//*************************************************************//
//        II. BÀI TOÁN PHÂN TÍCH RA THỪA SỐ NGUYÊN TỐ          //
//*************************************************************//
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace Chuong4
{
    class PhanTich
    {
        private string result;

        public string Result
        {
            get { return result; }
            set { result = value; }
        }
        public PhanTich(BigInteger n)
        {
            this.N = n;

        }
        BigInteger n;

        public BigInteger N
        {
            get { return n; }
            set { n = value; }
        }
        BigInteger x;

        public BigInteger X
        {
            get { return x; }
            set { x = value; }
        }
        BigInteger y;

        public BigInteger Y
        {
            get { return y; }
            set { y = value; }
        }

        // Phương pháp Fermat
        public string Fermat()
        {
            BigInteger sqrt = (BigInteger)(Math.Sqrt((double)n));
            if ((Math.Sqrt((double)n)) - (double)sqrt > 0.0000005)
                sqrt++;
            BigInteger temp = sqrt * sqrt - n;
            BigInteger temp2 = (BigInteger)(Math.Sqrt((double)temp));
            while (Math.Sqrt((double)temp) - (double)temp2 > 0.0000005)
            {
                sqrt++;
                temp = sqrt * sqrt - n;
                temp2 = (BigInteger)(Math.Sqrt((double)temp));
            }
            this.X = sqrt + temp2;
            this.Y = sqrt - temp2;

            if (this.Y == 1)
            {
                result += X.ToString()+" ";
            }
            else
            {
                n = sqrt + temp2;
                Fermat();
                n = sqrt - temp2;
                Fermat();
            }
            return result;
        }

        // Phương pháp Monte Carlo
        public void MonteCarlo(int maxSize)
        {
            BigInteger[] m = new BigInteger[maxSize + 2];
            m[0] = GenerateLargeNumbers(this.N.ToString().Length);
            m[1] = (m[0] * m[0] + 1) % this.N;
            m[2] = (m[1] * m[1] + 1) % this.N;
            int i = 2;
            while (BigInteger.GreatestCommonDivisor(m[i] - m[i / 2], this.N) == 1)
            {
                i++;
                m[i] = (m[i - 1] * m[i - 1] + 1) % this.N;
                i++;
                m[i] = (m[i - 1] * m[i - 1] + 1) % this.N;
            }
            this.X = BigInteger.GreatestCommonDivisor(m[i] - m[i / 2], this.N);
            this.Y = n / this.X;
        }

        // Phương pháp Rho
        public void Rho()
        {
            SoNguyenTo snt = new SoNguyenTo();
            int i = 2;
            BigInteger r = GenerateLargeNumbers(this.N.ToString().Length);
            r = snt.ModLuyThua(r, i, this.N);
            while (BigInteger.GreatestCommonDivisor(r - 1, this.N) == 1)
            {
                i++;
                r = snt.ModLuyThua(r, i, n);
            }

            this.X = BigInteger.GreatestCommonDivisor(r - 1, this.N);
            this.Y = this.N / this.X;
        }

        //Hàm khởi tạo số nguyên bất kỳ có số chữ số nhất định
        public static BigInteger GenerateLargeNumbers(int length)
        {
            string numbers = "";
            Random random = new Random(DateTime.Now.Millisecond);
            if (length <= 0) length = random.Next(10) + 1;
            for (int i = 0; i < length; i++)
            {
                numbers += random.Next(0, 10).ToString();
            }

            BigInteger number = BigInteger.Parse(numbers);
            return number;
        }
        
    }
}
